/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-16
 * Time: 22:56
 */
class Trie{
    public Trie[] arr;
    public Trie(){
        // 前 26 个表示对应的字母, 最后一个表示 结束标记
        this.arr = new Trie[27];
    }
}

public class Solution {
    public Trie root = new Trie();
    public int minimumLengthEncoding(String[] words) {
        int maxLen = 0;
        for (String s: words) {
            Trie cur = root; // 记住每个单词都要从头开始
            int len = 0; // 记录被包含的单词的长度, 以便计算差值
            boolean flag = false; // 记录这个单词是不是使得前缀树添加了新的节点
            boolean modify = false; // 记录长度是否已经更改
            for (int i = s.length() - 1; i >= 0; i--) {
                char c = s.charAt(i);
                // 字母没对上
                if (cur.arr[c - 'a'] == null){
                    // 要及时更改长度, 长度没有更改过
                    if (!modify){
                        if (cur.arr[26] != null){
                            // 如果这个字符串很长, 以之前的某个单词结尾
                            // 那么最大长度就要加上差值
                            maxLen += (s.length() - len);
                            // 因为新的单词包含了之前的单词,
                            // 所以要及时将这个单词删除, 以免再次被其他单词包含时重复计算长度
                            cur.arr[26] = null;
                        }else{
                            // 不能包含之前的某个单词
                            maxLen += s.length() + 1; // 1 是多加的 '#'
                        }
                        // 只要一旦对不上, 及时更改 maxLen, 之后就不再更改
                        modify = true;
                    }
                    cur.arr[c - 'a'] = new Trie();
                    // 增添了新的节点, 那么后面就要为这个单词记录一个结尾标志
                    flag = true;
                }
                cur = cur.arr[c - 'a'];
                len++;
            }
            // 单词放完了, 记住放结束标记
            if (flag){
                // 只有这个节点导致新的节点的增加, 才用 添加结束标记
                cur.arr[26] = new Trie();
            }
        }
        return maxLen;
    }
}
